package org.shj.suanfa

/**
 * 给定n个数的数组，找到所有长度大于等于k的连续子数组中平均值最大的那个。返回那个最大的平均值
 * 1 <= k <= n<= 10000, 数组中的元素在范围[-10000, 10000]之间，最后返回的答案的误差应在 10^(-5)以内
 */
object S004 {
  def main(args: Array[String]): Unit = {
    //var arr = Array(10, 34, -20, 100, 34, -200, 59, 78, -23, 56, 90, 124, -234)
    val arr = Array(1,12, -5, -6, 50, 3)
    method(arr, 4)
    
  }
  
  /*def method1(arr: Array[Int] , k: Int){
    var begin = 0
    var end = k -1
    var maxavg = 0.0
    var curXielv = 0.0
    var sum = 0.0
    
    for(i <- 0 to k - 1){
      sum += arr(i)
      curXielv = sum / k
    }
    
    for(i <- k to arr.length - 1){
      if(arr(i) > curXielv){
        sum += arr(i)
        end = i
        curXielv = sum / (end - begin + 1)
      }else{
        
      }
    }
    
    println("begin: " + begin + "; end: " + end + "; avg: " + maxavg)
  }*/
  
  // O(n^2)
  def method(arr: Array[Int], k: Int){
    
    var sum = 0.0
    var begin = 0
    var end = 0
    var avg = 0.0
    var maxavg = 0.0
    var cnt = 0
    import scala.math.min
    var flag = true
    
    for(i <- 0 to arr.length -1 if flag){      
      
      if(i+k-1 > arr.length -1){        
        flag = false
      }else{
        cnt = 0
        sum = 0.0
        for(j <- i to i+k-1){
          sum += arr(j)
          cnt += 1
        }
        avg = sum / cnt
        if(i == 0 || avg > maxavg){
          begin = i
          end = i + k -1
          maxavg = avg
        }
        
        for(j <- (i+k) to arr.length -1){
          cnt += 1
          sum += arr(j)
          avg = sum / cnt
          if(avg > maxavg){
            begin = i
            end = j 
            maxavg = avg
          }
        }
      }
      
    }
    println("begin: " + begin + "; end: " + end + "; avg: " + maxavg)
  }
}